package com.cdream.basic.algorithm.leetcode.bfs;

import cn.hutool.json.JSONUtil;

import java.util.*;

/**
 * @author cdream
 * @date 6/26/21
 */
public class Question773 {
    public static void main(String[] args) {
        System.out.println(new Question773().slidingPuzzle(new int[][]{{3, 2, 4}, {1, 5, 0}}));
    }
    private int[][] k = new int[][]{{1, 2, 3}, {4, 5, 0}};



    public int slidingPuzzle(int[][] board) {
        if (isOrder(board)) {
            return 0;
        }
        Set<String> used = new HashSet<>();
        used.add(arrayToString(board));
        Queue<int[][]> queue = new LinkedList<>();
        queue.offer(board);
        int i = 0;
        while (!queue.isEmpty()) {

            i++;
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                System.out.println("----------");
                int[][] poll = queue.poll();
                List<int[][]> intList = allPossible(poll);
                for (int k = 0; k < intList.size(); k++) {
                    int[][] b = intList.get(k);
                    if (isOrder(b)) {
                        return i;
                    }
                    String s = arrayToString(b);
                    if (!used.contains(s)) {
                        queue.offer(b);
                        used.add(s);
                    }
                }
                System.out.println(used);
                System.out.println(JSONUtil.toJsonStr(queue));

            }

        }
        return -1;
    }

    private List<int[][]> allPossible(int[][] board) {
        int[] zero = findZero(board);
        List<int[][]> res = new ArrayList<>();
        int[][] s1 = getSwapString(board, zero, new int[]{zero[0] + 1, zero[1]});
        int[][] s2 = getSwapString(board, zero, new int[]{zero[0] - 1, zero[1]});
        int[][] s3 = getSwapString(board, zero, new int[]{zero[0], zero[1] + 1});
        int[][] s4 = getSwapString(board, zero, new int[]{zero[0], zero[1] - 1});
        if (s1 != null) res.add(s1);
        if (s2 != null) res.add(s2);
        if (s3 != null) res.add(s3);
        if (s4 != null) res.add(s4);
        return res;
    }

    private int[][] getSwapString(int[][] board, int[] zero, int[] ints) {
        if (ints[0] < 0 || ints[0] > 1 || ints[1] < 0 || ints[1] > 2) {
            return null;
        }
        int[][] res = new int[board.length][board[0].length];
        for (int i = 0; i < res.length; i++) {
            for (int j = 0; j < res[0].length; j++) {
                res[i][j] = board[i][j];
            }
        }
        int temp = res[zero[0]][zero[1]];
        res[zero[0]][zero[1]] = res[ints[0]][ints[1]];
        res[ints[0]][ints[1]] = temp;
        return res;

    }

    private String arrayToString(int[][] board) {
        StringBuilder sb = new StringBuilder();
        for (int[] ints : board) {
            for (int j = 0; j < board[0].length; j++) {
                sb.append(ints[j]);
            }
        }
        return sb.toString();
    }

    private int[] findZero(int[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == 0) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }


    boolean isOrder(int[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (k[i][j] != board[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
}
